#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	void inorder(TreeNode *p,vector<int> &res) {
		if (p == NULL)
			return;
		inorder(p->left, res);
		res.push_back(p->val);
		inorder(p->right, res);
	}

	vector<int> inorderTraversal(TreeNode* root) {
		vector<int> res;
		inorder(root, res);
		return res;
	}

	vector<int> inorderTraversalByIterator(TreeNode* root) {
		vector<int> res;
		TreeNode *p = root;
		stack<TreeNode*> stk;
		while (p||!stk.empty()) {
			while (p) {
				stk.push(p->left);
				p = p->left;
			}
			p=stk.top();
			stk.pop();
			res.push_back(p->val);
			p = p->right;
		}
		return res;
	}
};


void main() {
	TreeNode root(1), l1(2), l2(3);
	root.right = &l1;
	l1.right = &l2;
	Solution s;
	s.inorderTraversal(&root);
}